//
//  main.c
//  字符串匹配 RK 算法
//
//  Created by Shawn Li on 2020/5/13.
//  Copyright © 2020 Shawn. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 RK 算法
 
 前提：此处假定主串和模式串仅含有26个小写字母。这样假设是为了好理解，其他情况换掉这里的 26 为 N 即可。
 
 思想：
 由于只有 26 个不同的字符，所以每个字符串等价为使用了 26 进制来表示的数字，如果我们使得 1 <=> a, 2<=> b,....，那么我们可以计算出这个 26 进制的数在十进制下的值。
 例如 adc 就相当于是 26 进制下的数字，转为 10 进制下的值为：
 abc = 1 * 26^2 + 2 * 26^1 + 3 * 26^0 = 731
 
 我们可以把这个值记为这个字符串的标志值。其实这就是哈希的思想，这样的转化就是一个哈希算法，这个值称为这个字符串的哈希值。
 
 由此易得：如果哈希值不同，那么字符串一定不同；但是在哈希值相同的情况下也有可能字符串不同，这时我们可以增加一次校验即可。
 
 RK 的算法正式基于此：
 假设我们有某个hash函数可以将字符串转换为一个整数，则hash结果不同的字符串肯定不同，但hash结果相同的字符串则很有可能相同（存在小概率不同的可能）。
 
 ####将两个字符串的比较转为两个数字的比较，这是 RK 算法的亮点。####
 
 在这样前提下，设 主串长度为 n; 模式串长度为 m,
 那么主串可以拆解为 (n - m + 1) 个与模式串长度相等的子串。
 然后我们只需要比较这些串的值即可。
 
 例如：主串s为：126783 模式串t为 678
 
 n = 6; m = 3;
 
 主串拆解的子串有：
 126 = 1 * 10^2 + 2 * 10^1 + 6 * 10^0
 267 = 2 * 10^2 + 6 * 10^1 + 7 * 10^0
 678 = 6 * 10^2 + 7 * 10^1 + 8 * 10^0
 783 = 7 * 10^2 + 8 * 10^1 + 3 * 10^0
 
 在计算中我们不难发现，我们在计算了“126”的值之后需要再计算右移一位的子串“267”值，其中“26”的计算其实十分类似，只是由于其所在的位不同所以进制权重有所变化而已。
 
 即我们需要找寻如何根据 （下列表达式中 “_” 后的表达式为下标，x 为进制）
 
 hash(Si-m+1...Si)
 
 在O(1)的时间内求出
 
 hash(Si-m+2...Si+1)
 
 -----
 
 hash(S_(i-m+1)...S_i)
 =
 S_(i-m+1)*x^(m-1) + S_(i-m+2)*x^(m-2) + ... + S_(i-1)*x + Si
 
 =>
 
 hash(S_(i-m+2)...S_(i+1))
 =
 S_(i-m+2_*x^(m-1) + S_(i-m+3)*x^(m-2) + ... + S_i*x + S_(i+1)
 =
 (hash(S_(i-m+1)...S_i) - S_(i-m+1)*x^(m-1)) * x + S_(i+1)
 
 
 白话总结一下加强理解，读不懂就看上面的公式：
 如果 s_i 的哈希值是 v_i，那么 v_i 减去 s_i 最高位的进制权重，然后剩下的值就是 所有 除去最高位字符 的 剩余字符的 进制权重和，在新的字符里，他们要集体左移一位，那么这个值就需要乘以进制，再加上新补上的最后一位的进制权重就是新的 s_i+1 的哈希值 v_i+1。
 
 v_i+1 = N * (v_i - (s_i 最高位的进制权重)) + （s_i+1 最末位的进制权重）
 
 
 #### 这是 RK 算法的第二个亮点。 ####
 只需要计算出第一个子串的哈希值，就能在 o(1) 的时间内计算出下一个，使得算法的效率大大提升。
 
 */
 

// 这是包含字符集合的长度
#define N 26

typedef int Status;

#define SUCCESS 1
#define ERROR 0


/// 哈希值一样的时候可能原串并不相等，这就是哈希冲突。为了解决这个问题，我们需要再次校验一下。
/// @param s 主串
/// @param keyIndex 主串中匹配到的模式串的起始位置
/// @param t 模式串
/// @param m 模式串的长度
Status isCheckMatch(char *s, int keyIndex, char *t, int m){
    
    int index_s, index_t;
    for (index_s = keyIndex, index_t = 0; index_s != keyIndex + m && index_t != m; index_s++, index_t++) {
        if (s[index_s] != t[index_t]) {
            return ERROR;
        }
    }
    return SUCCESS;
}


/// 获取 N 进制下 单位最高位进制权重
/// 例如： 321 中  10 进制下 单位最高位进制权重 就是 3 所在的位置的权重为 10^(3-1) = 100;
/// @param m 模式串的长度
int getHightValue(int m){
    int value = 1;
    for (int i = 0; i < m - 1; i++) {
        value *= N;
    }
    return value;
}


/// 字符串匹配 RK 算法
/// @param s 主串
/// @param t 模式串
/// @param keyIndex 找到的结果
Status stringMatch_RK(char *s, char *t, int *keyIndex){
    
//    获取两个串的长度
    int n = (int)strlen(s);
    int m = (int)strlen(t);
    
    printf("主串长度为：%d,模式串长度为：%d\n", n, m);
    
//    模式串的哈希值
    long long t_hashValue = 0;
//    子串的哈希值   注意：子串是由主串拆解为的 与模式串等长 的字符串
    long long s_sub_hashValue = 0;
    
//    求得模式串和第一个子串的哈希值  第一个子串就是主串的前 m 位构成的字符串，后面的每个子串就是这个长度一直往后移位就是。
    for (int i = 0; i < m; i++) {
        t_hashValue = (N * t_hashValue + (t[i] - 'a'));
        
        s_sub_hashValue = (N * s_sub_hashValue + (s[i] - 'a'));
    }
    
//    这是最高位的单位进制权重
    int hightValue = getHightValue(m);
    
    for (int i = 0; i <= n - m; i++) {
        if (t_hashValue == s_sub_hashValue) {
//            如果相等了需要考虑到哈希冲突
            if (isCheckMatch(s, i, t, m)) {
//                加 1 是位数，不加 1 就是下标值，任君抉择
//                *keyIndex = i + 1;
                *keyIndex = i;
                return SUCCESS;
            }
        }
//        如果不相等那么就将子串往后移动一位
        s_sub_hashValue = (s_sub_hashValue - (s[i] - 'a') * hightValue) * N + (s[i + m] - 'a');
    }
    
    *keyIndex = -1;
    return ERROR;
}



int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    char *buf="abcababcabx";
    char *ptrn="abcabx";
    int keyIndex = -1;
    
    
    printf("主串为%s\n",buf);
    printf("模式串为%s\n",ptrn);
    
    if (stringMatch_RK(buf, ptrn, &keyIndex)){
        printf("find success! The key index : %d\n",keyIndex);
    }else{
        printf("find fail!\n");
    }
    
    return 0;
}
